package week4;

import base.TreeNode;

/**
 *
 *
 * 538. 把二叉搜索树转换为累加树
 * https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了27.77% 的用户
 * 内存消耗：38.4 MB, 在所有 Java 提交中击败了90.26% 的用户
 * 通过测试用例：215 / 215
 * 炫耀一下:
 *
 *
 */
public class Week4ConvertBstToGreaterTree {

    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        // convert(root, sum);
        if(root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }

        return root;
    }

    public TreeNode convert(TreeNode root, int sum) {
        if(root != null) {
            convert(root.right, sum);
            sum += root.val;
            root.val = sum;
            convert(root.left, sum);
        }
        return root;
    }
}
